A network processor generally controls the flow of packets between a physical transmission medium, such as a physical layer portion of, e.g., an asynchronous transfer mode (ATM) network or synchronous optical network (SONET), and a switch fabric in a router or other type of packet switch. Such routers and switches generally include multiple network processors, e.g., arranged in the form of an array of line or port cards with one or more of the processors associated with each of the cards.
Many conventional routers and switches are configured to store, for a given packet being processed, substantially the entire packet, until that packet is finally transmitted to its destination or dropped. The packet is usually stored in a router or switch memory external to the associated network processor. The amount of time the given packet may be kept in external memory is influenced by the basic processing time of the router or switch, the quality of service applied to the packet, the particular protocol layers to be analyzed, and the congestion of the port or other communication channel to which the packet is directed.
High-speed routers and switches will typically store in on-chip memory within the network processor some portion of a given packet being processed by that network processor. This greatly enhances the performance of the router or switch by not requiring it to access the larger external memory holding the entire packet, in that the external memory is slower and more band-limited than the on-chip memory.
A network processor generally must perform packet classification operations in order to determine the particular processing operations to be applied to a given packet. Such classification is preferably performed on the portions of the packets stored in the on-chip or internal memory of the processor.
In accordance with conventional practice, the above-noted packet classification is performed in a linear or sequential manner. That is, the bits of the packet are processed sequentially, starting from the beginning of the packet, until a sufficient number of bits have been processed to allow a classification decision to be made. Unfortunately, this type of sequential classification is generally unsuitable for use with embedded protocols.
For example, consider a packet with three embedded protocols in which determination of the third protocol requires that a parity check of the entire packet be performed, including the bits that have already been processed. This type of situation creates a problem in that the sequential classification process must return to the beginning of the packet and be re-started in a manner which will satisfy the third protocol. As a result, the throughput of the processor may be significantly reduced.
As is apparent from the foregoing, a need exists for techniques for performing packet classification in a network processor or other type of processor, so as to accommodate the embedded protocols situation described above as well as other situations in which conventional sequential classification is deficient.